package com.cat.chapter050;

import java.util.Arrays;

/**
 * @author cat
 * @description https://leetcode.cn/problems/heaters/
 * @create 2025/7/21 14:18
 * @since JDK17
 */

public class Solution05 {
    public boolean isVaild(int[] h, int[] g, int lim) {
        int i, j, n = g.length, m = h.length;
        for (i = 0, j = 0; j < n && i < m; ) {
            if (g[j] - lim <= h[i] && h[i] <= g[j] + lim) {
                i++;
            } else {
                j++;
            }
        }
        return i == m;
    }


    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int mid = 0, l = 0, n = houses.length, r = houses[n - 1], m = heaters.length;
        while (l + 1 < r) { //
            mid = (l + r) / 2;
            if (isVaild(houses, heaters, mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
}
